package com.zzh.dp;

//一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
//
// 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
//
// 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
//
//
//
// 网格中的障碍物和空位置分别用 1 和 0 来表示。
//
// 说明：m 和 n 的值均不超过 100。
//
// 示例 1:
//
// 输入:
//[
//  [0,0,0],
//  [0,1,0],
//  [0,0,0]
//]
//输出: 2
//解释:
//3x3 网格的正中间有一个障碍物。
//从左上角到右下角一共有 2 条不同的路径：
//1. 向右 -> 向右 -> 向下 -> 向下
//2. 向下 -> 向下 -> 向右 -> 向右
//
// Related Topics 数组 动态规划
// 👍 350 👎 0

public class No63_uniquePathsWithObstacles {
    public static void main(String[] args) {
        No63Solution solution = new No63Solution();
        int i = solution.uniquePathsWithObstacles(new int[][]{
                {1, 0, },
//                {0, 1, 0},
//                {0, 0, 0}
        });
        System.out.println(i);
    }
}

class No63Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid[0][0]==1){
            return 0;
        }
        int mark=-1;
        for (int i=0;i<obstacleGrid.length;i++){
            if (obstacleGrid[i][0]==1){
                mark=i;
                break;
            }
        }
        if (mark!=-1){
            for (int i=mark;i<obstacleGrid.length;i++){
                obstacleGrid[i][0]=-1;
            }
        }
        mark=-1;
        for (int i=0;i<obstacleGrid[0].length;i++){
            if (obstacleGrid[0][i]==1){
                mark=i;
                break;
            }
        }
        if (mark!=-1){
            for (int i=mark;i<obstacleGrid[0].length;i++){
                obstacleGrid[0][i]=-1;
            }
        }
//        for (int i=0;i<obstacleGrid.length;i++) {
//            System.out.println(Arrays.toString(obstacleGrid[i]));
//        }

        for (int row=0;row<obstacleGrid.length;row++){
            for (int col=0;col<obstacleGrid[0].length;col++){
                if (obstacleGrid[row][col]==1||obstacleGrid[row][col]==-1){
                    obstacleGrid[row][col]=-1;
                }else if (row==0||col==0){
                    obstacleGrid[row][col]=1;
                }else {
                    obstacleGrid[row][col]=(obstacleGrid[row-1][col]==-1?0:obstacleGrid[row-1][col])
                            +(obstacleGrid[row][col-1]==-1?0:obstacleGrid[row][col-1]);
                }
            }
        }
//        for (int i=0;i<obstacleGrid.length;i++) {
//            System.out.println(Arrays.toString(obstacleGrid[i]));
//        }
        return Math.max(obstacleGrid[obstacleGrid.length-1][obstacleGrid[0].length-1],0);
    }
}
